export const getSequence = (arr: number[]): number[] => {
  // 缓存数组总长度
  const len = arr.length;
  // 默认连续的最终结果 组成的索引
  const result = [0];
  let resultLastIndex;
  let start, end, middle;
  // ! 用来标识数组索引
  let p: Array<number> = arr.slice(0);
  // 1.将数组中的每一个元素和子序列中最后一个元素作比较
  for (let index = 0; index < len; index++) {
    const arrIndex = arr[index];
    // vue3 diff序列中不会出现0的情况,如果序列中出现0 说明时新增的,忽略
    if (arrIndex !== 0) {
      resultLastIndex = result[result.length - 1];
      if (arrIndex > arr[resultLastIndex]) {
        // 2.如果当前元素比子序列中最后一个元素大，那么就将当前元素添加到子序列中
        result.push(index);
        // !让子序列最后一项记住前一项的索引
        p[index] = resultLastIndex;
        // 因为是保持的递增的态势
        continue;
      }

      // 3. 到这里会出现当前项比最后一项小，那么需要在子序列中找到第一个比他小的项，然后将他替换成当前项的索引
      //    此时result 结果值为 [0 ,1, 2 ] 对应 结果为 2 5 8
      start = 0;
      end = result.length - 1;
      // !二分查找
      while (start < end) {
        // middle = Math.floor((start + end) / 2);
        middle = ((start + end) / 2) | 0;
        if (arr[result[middle]] < arrIndex) {
          start = middle + 1;
        } else {
          end = middle;
        }
      }
      // end 就是第一个比当前值大的值的索引
      if (arrIndex < arr[result[end]]) {
        // ! 记住换的那个人的前一项的索引
        p[index] = result[end - 1];
        result[end] = index;
      }
    }
  }
  // [ 0, 7, 4, 5, 6 ]
  // [2, 1, 8, 4, 6, 7];
  // console.log('追溯前===', result);
  // ! 开始追溯 恢复最长递增子序列个元素在原数组中的索引
  let l = result.length;
  let last = result[l - 1]; // 最后一项的索引
  while (l-- > 0) {
    result[l] = last;
    last = p[last];
  }
  // [ 0, 3, 4, 5, 6 ]
  // [ 0, 1, 3, 4, 6, 7 ]
  // console.log('追溯后===', result);
  return result;
};
const arr = [2, 5, 8, 4, 6, 7, 9, 3];
const arr1 = [2, 3, 1, 5, 6, 8, 7, 9, 4, 1];
const result = getSequence(arr1);
